{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #目标和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findTargetSumWays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #目标和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个正整数数组 <code>nums</code> 和一个整数 <code>target</code> 。</p>\n",
    "\n",
    "<p>向数组中的每个整数前添加&nbsp;<code>&#39;+&#39;</code> 或 <code>&#39;-&#39;</code> ，然后串联起所有整数，可以构造一个 <strong>表达式</strong> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>nums = [2, 1]</code> ，可以在 <code>2</code> 之前添加 <code>&#39;+&#39;</code> ，在 <code>1</code> 之前添加 <code>&#39;-&#39;</code> ，然后串联起来得到表达式 <code>&quot;+2-1&quot;</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回可以通过上述方法构造的、运算结果等于 <code>target</code> 的不同 <strong>表达式</strong> 的数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,1,1,1,1], target = 3\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>一共有 5 种方法让最终目标和为 3 。\n",
    "-1 + 1 + 1 + 1 + 1 = 3\n",
    "+1 - 1 + 1 + 1 + 1 = 3\n",
    "+1 + 1 - 1 + 1 + 1 = 3\n",
    "+1 + 1 + 1 - 1 + 1 = 3\n",
    "+1 + 1 + 1 + 1 - 1 = 3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1], target = 1\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 20</code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= sum(nums[i]) &lt;= 1000</code></li>\n",
    "\t<li><code>-1000 &lt;= target &lt;= 1000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 494&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/target-sum/\">https://leetcode-cn.com/problems/target-sum/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [YaVDxD](https://leetcode.cn/problems/YaVDxD/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [YaVDxD](https://leetcode.cn/problems/YaVDxD/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1,1,1,1]\\n3', '[1]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        target += sum(nums)\n",
    "        if target < 0 or target % 2:\n",
    "            return 0\n",
    "        target //= 2\n",
    "        dp = [ 0 ] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        for i, x in enumerate(nums):\n",
    "            for j in range(target, x-1, -1):\n",
    "                dp[j] += dp[j-x]\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        if len(nums)==1:\n",
    "            ans=0\n",
    "            if nums[0]==target:\n",
    "                ans+=1\n",
    "            if nums[0]==-target:\n",
    "                ans+=1\n",
    "            return ans\n",
    "        n1=len(nums)//2 \n",
    "        n=len(nums)\n",
    "        cnt=Counter()\n",
    "        ans=0\n",
    "        def f1(x):\n",
    "            res=0\n",
    "            for i in range(n1):\n",
    "                if x>>i&1:\n",
    "                    res+=nums[i]\n",
    "                else:\n",
    "                    res-=nums[i]\n",
    "            cnt[res]+=1\n",
    "            return \n",
    "        def f2(x):\n",
    "            nonlocal ans\n",
    "            res=0\n",
    "            for i in range(n-n1):\n",
    "                if x>>i&1:\n",
    "                    res+=nums[i+n1]\n",
    "                else:\n",
    "                    res-=nums[i+n1]\n",
    "            ans+=cnt[target-res]\n",
    "            return \n",
    "        for i in range(2<<(n1-1)):\n",
    "            f1(i)\n",
    "\n",
    "        for i in range(2<<(n-n1-1)):\n",
    "            f2(i)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "\n",
    "        D = defaultdict(int)\n",
    "\n",
    "        for i, a in enumerate(nums):\n",
    "            if len(D) == 0:\n",
    "                D[a] += 1\n",
    "                D[-a] += 1\n",
    "                continue\n",
    "            newD = defaultdict(int)\n",
    "            for k, v in D.items():\n",
    "                newD[k+a] += v\n",
    "                newD[k-a] += v\n",
    "            D = copy.deepcopy(newD)\n",
    "            # print(D)\n",
    "        return D[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        self.memo = dict()\n",
    "        return self.dp(nums, 0, target)\n",
    "\n",
    "    def dp(self, nums, i, remain):\n",
    "        if i == len(nums):\n",
    "            if remain == 0:\n",
    "                return 1\n",
    "            return 0\n",
    "        \n",
    "        key = str(i) + ',' + str(remain)\n",
    "        if key in self.memo:\n",
    "            return self.memo[key]\n",
    "\n",
    "        result = self.dp(nums, i+1, remain-nums[i]) + self.dp(nums, i+1, remain+nums[i])\n",
    "\n",
    "        self.memo[key] = result\n",
    "\n",
    "        return result "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        memo={}\n",
    "        def dfs(cur_sum,idx,memo):\n",
    "            if idx<len(nums) and (cur_sum,idx) not in memo:\n",
    "                memo[(cur_sum,idx)]=dfs(cur_sum+nums[idx],idx+1,memo)+dfs(cur_sum-nums[idx],idx+1,memo)\n",
    "            return memo.get((cur_sum,idx),int(cur_sum==target))\n",
    "        return dfs(0,0,memo)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums = [0] + nums\n",
    "        dp = [defaultdict(int) for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(-1000, 1001):\n",
    "                dp[i][j] += dp[i - 1][j + nums[i]] + dp[i - 1][j - nums[i]]\n",
    "        return dp[-1][target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, t):\n",
    "            if idx == n:\n",
    "                if t == target:\n",
    "                    return 1\n",
    "                return 0\n",
    "            # 后面全取正也到不了 或者说 后面全取负也到不了\n",
    "            if abs(target - t) > presum[-1] - presum[idx]:\n",
    "                return 0\n",
    "            return dfs(idx+1, t+nums[idx]) + dfs(idx+1, t-nums[idx])\n",
    "        n = len(nums)\n",
    "        presum = [0] * (n+1)\n",
    "        for i in range(n):\n",
    "            presum[i+1] = presum[i] + nums[i]\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def backtrack(pos, cur_sum):\n",
    "            if pos == n:\n",
    "                if cur_sum == target:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            \n",
    "            if sum(nums[pos:]) + cur_sum < target or -sum(nums[pos:]) + cur_sum > target:\n",
    "                return 0\n",
    "            \n",
    "            left = backtrack(pos+1, cur_sum-nums[pos])\n",
    "            right = backtrack(pos+1, cur_sum+nums[pos])\n",
    "            return left + right\n",
    "        return backtrack(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [defaultdict(int) for _ in range(n)]\n",
    "        sumv = sum(nums)\n",
    "        dp[0][nums[0]] = 1\n",
    "        dp[0][-nums[0]] += 1\n",
    "        for i in range(1, n):\n",
    "            for v in range(-sumv, sumv + 1):\n",
    "                # dp[i][v] = dp[i - 1][v + nums[i]] + dp[i - 1][v - nums[i]]\n",
    "                dp[i][v + nums[i]] += dp[i - 1][v]\n",
    "                dp[i][v - nums[i]] += dp[i - 1][v]\n",
    "        return dp[n - 1][target]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        total_val = [sum(nums)]\n",
    "        for i in range(0, len(nums) - 1):\n",
    "            total_val.append(total_val[-1] - nums[i])\n",
    "        # total_val = total_val[1:]\n",
    "\n",
    "        self.ans = 0\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, target):\n",
    "            if i == len(nums) - 1:\n",
    "                if target == 0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            if i >= 0 and abs(target) > abs(total_val[i]):\n",
    "                return 0\n",
    "            ans = 0\n",
    "            ans += dfs(i + 1, target - nums[i])\n",
    "            ans += dfs(i + 1, target + nums[i])\n",
    "            return ans\n",
    "\n",
    "        return dfs(-1, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        # 从nums中挑选任意个数, 使之等于target, 求共计有多少中选择\n",
    "        @lru_cache(None)\n",
    "        def dfs(start, target):\n",
    "            if target == 0:\n",
    "                return 1\n",
    "            if target < 0 or start == len(nums):\n",
    "                return 0\n",
    "\n",
    "            result = sum(dfs(i+1, target-nums[i]) for i in range(start, len(nums)) if nums[i] != 0)\n",
    "            return result\n",
    "\n",
    "        target_ = sum(nums) - target\n",
    "        if target_ == 0:\n",
    "            return 2 ** nums.count(0)\n",
    "        elif target_ < 0 or target_ % 2:\n",
    "            return 0\n",
    "        else:\n",
    "            result = 2 ** nums.count(0) * dfs(0, target_//2)\n",
    "            return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        dp = defaultdict(int) \n",
    "        left = -sum(nums) \n",
    "        right = sum(nums)\n",
    "        #边界条件 初始化 i=0 select nums[0]     \n",
    "        #dp[(0,nums[0])] , dp[(0,-nums[0])] = 1,1                #debug     \n",
    "        if nums[0] : dp[(0,nums[0])] , dp[(0,-nums[0])] = 1,1  \n",
    "        else : dp[(0,nums[0])] = 2\n",
    "        for i in range(1,n) :\n",
    "            for j in range(left,right+1):\n",
    "                    dp[(i,j)] = dp[(i-1,j-nums[i])] + dp[(i-1,j+nums[i])]\n",
    "\n",
    "        return dp[(n-1,target)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# ### my:dP(思路错误)\n",
    "# class Solution:\n",
    "#     def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "#         if sum(nums)<abs(target):return 0\n",
    "#         dp=[0]*(target+1)\n",
    "#         dp[0]=1\n",
    "#         n=len(nums)\n",
    "#         for x in range(n):\n",
    "#             cp=[0]*(target+1)\n",
    "#             for y in range(1,target+1):\n",
    "#                 cp[y]=cp[y-1]\n",
    "#                 if 1<=y-x<=target:\n",
    "#                     cp[y]+=dp[y-x]\n",
    "#                 if 1<=y+x<=target:\n",
    "#                     cp[y]+=dp[y+x]\n",
    "#             dp=cp\n",
    "#         return dp[target]\n",
    "\n",
    "# ###官思：DP\n",
    "# class Solution:\n",
    "#     def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "#         # if sum(nums)<abs(target):return 0\n",
    "#         # neg=(sum(nums)-target)//2\n",
    "#         su=sum(nums)\n",
    "#         ### eg:[7,9,3,8,0,2,4,8,3,9],0\n",
    "#         if su<target or (su-target)%2:return 0\n",
    "#         neg=(su-target)//2\n",
    "#         dp=[1]+[0]*neg\n",
    "#         n=len(nums)\n",
    "#         for i in range(1,n+1):\n",
    "#             cp=[0]*(neg+1)\n",
    "#             # cp[0]=dp[0]\n",
    "#             # if nums[i-1]==0:\n",
    "#             #     cp[0]+=dp[0]\n",
    "#             # for j in range(1,neg+1):\n",
    "#             for j in range(neg+1):### start from 0, eg[1,0],1\n",
    "#                 cp[j]=dp[j]\n",
    "#                 if j>=nums[i-1]:\n",
    "#                     cp[j]+=dp[j-nums[i-1]]\n",
    "#             dp=cp\n",
    "#         return dp[-1]\n",
    "\n",
    "# ### 官思：DP--优化版\n",
    "# class Solution:\n",
    "#     def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "#         su=sum(nums)\n",
    "#         if (su-target)%2 or su<target:return 0\n",
    "#         neg=(su-target)//2\n",
    "#         dp=[1]+[0]*neg \n",
    "#         for num in nums:\n",
    "#             # for j in range(neg,-1,-1):\n",
    "#             for j in range(neg,num-1,-1): ### 剔除多余遍历\n",
    "#                 # if j>=num:\n",
    "#                 dp[j]+=dp[j-num]\n",
    "#         return dp[-1]\n",
    "\n",
    "# ### S-code\n",
    "# class Solution:\n",
    "#     def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "#         #pos neg\n",
    "#         #pos+neg=total\n",
    "#         #pos-neg=target\n",
    "        \n",
    "#         total=sum(nums)\n",
    "#         if abs(target)>total:\n",
    "#             return 0\n",
    "#         if (total+target)%2==1:\n",
    "#             return 0\n",
    "#         elif (total-target)%2==1:\n",
    "#             return 0\n",
    "#         pos=(total+target)//2\n",
    "#         neg=(total-target)//2\n",
    "\n",
    "#         cap=min(pos,neg)\n",
    "        \n",
    "\n",
    "\n",
    "#         dp=[0]*(cap+1)\n",
    "#         dp[0]=1\n",
    "#         for num in nums:\n",
    "#             for j in range(cap,num-1,-1):\n",
    "#                 dp[j]+=dp[j-num]\n",
    "        \n",
    "#         return dp[cap]\n",
    "\n",
    "\n",
    "# ###回溯---超时\n",
    "# # from functools import lru_cache\n",
    "# class Solution:\n",
    "#     def findTargetSumWays(self,nums,target):\n",
    "#         su=sum(nums)\n",
    "#         n=len(nums)\n",
    "#         if (su-target)%2 or su<abs(target):return 0\n",
    "#         self.ans=0\n",
    "#         # @functools.lru_cache(None)# 不能使用，结果出错[0,35,32,3,4,16,12,25,47,9,14,29,7,26,17,42,21,23,48,18]，20正确结果：20 返回：1\n",
    "\n",
    "#         def dfs(i,cul):\n",
    "#             if i==n:\n",
    "#                 if cul==target:\n",
    "#                     self.ans+=1\n",
    "#                 return\n",
    "#             dfs(i+1,cul+nums[i])\n",
    "#             dfs(i+1,cul-nums[i])\n",
    "\n",
    "#         dfs(0,0)\n",
    "#         return self.ans\n",
    "\n",
    "# ### 改造版：记忆搜索（参考如下）\n",
    "# # https://leetcode.cn/problems/YaVDxD/solution/by-flix-n3q2/\n",
    "# class Solution:\n",
    "#     def findTargetSumWays(self,nums,target):\n",
    "#         su=sum(nums)\n",
    "#         n=len(nums)\n",
    "#         if (su-target)%2 or su<abs(target):return 0\n",
    "\n",
    "#         mp={}\n",
    "#         def dfs(i,cul):\n",
    "#             if i==n:\n",
    "#                 if cul==target:\n",
    "#                     return 1\n",
    "#                 return 0\n",
    "#             if (i,cul) in mp:\n",
    "#                 return mp[(i,cul)]\n",
    "\n",
    "#             cnt=0\n",
    "#             cnt+=dfs(i+1,cul+nums[i])\n",
    "#             cnt+=dfs(i+1,cul-nums[i])\n",
    "\n",
    "#             mp[(i,cul)]=cnt\n",
    "#             return cnt\n",
    "\n",
    "#         return dfs(0,0)\n",
    "\n",
    "### 灵茶山（0-1背包）记忆化搜索\n",
    "### 解题思路。假设1.正数和p,2.负数和绝对值 sum(nums)-p,得p-(s-p)=target ,得p=（target+s)//2\n",
    "###　由此改造成nums中选哪些值为正数相加得p的方案数\n",
    "class Solution:\n",
    "    def findTargetSumWays(self,nums,target):\n",
    "        n=len(nums)\n",
    "        su=sum(nums)\n",
    "        if su<abs(target):return 0\n",
    "        target+=su \n",
    "        if target%2:return 0\n",
    "        target//=2\n",
    "        # if target%2:return 0\n",
    "        mp={}\n",
    "\n",
    "        def dfs(i,c):\n",
    "            if i<0:\n",
    "                return 1 if c==0 else 0\n",
    "            if (i,c) in mp:\n",
    "                return mp[(i,c)]\n",
    "            if c<nums[i]: ###　不选nums[i]\n",
    "                # return dfs(i-1,c)         \n",
    "                mp[(i,c)]=dfs(i-1,c)\n",
    "                return mp[(i,c)]\n",
    "            # return dfs(i-1,c)+dfs(i-1,c-nums[i])\n",
    "            mp[(i,c)]=dfs(i-1,c)+dfs(i-1,c-nums[i])\n",
    "            return mp[(i,c)]\n",
    "        return dfs(n-1,target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        t = sum(nums) - target\n",
    "        if t&1 or t < 0:\n",
    "            return 0\n",
    "        t //= 2\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(i,j):\n",
    "            if i<0:               \n",
    "                return 0 if j else 1\n",
    "\n",
    "            ans = dp(i-1,j)\n",
    "            if j >= nums[i]:\n",
    "                ans += dp(i-1, j-nums[i])\n",
    "            return ans\n",
    "\n",
    "        return dp(len(nums)-1, t)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        n=len(nums)\n",
    "        dt=dict()\n",
    "        def f(i,j):\n",
    "            nonlocal dt\n",
    "            if (i,j) in dt:\n",
    "                return dt[(i,j)]\n",
    "            if i==0 :\n",
    "                if j==0:\n",
    "                    ans=1\n",
    "                else:\n",
    "                    ans= 0\n",
    "            elif j>sum(nums[0:i]) or j<-sum(nums[0:i]):\n",
    "                ans= 0\n",
    "           \n",
    "            else:\n",
    "                ans=f(i-1,j-nums[i-1])+f(i-1,j+nums[i-1])\n",
    "            dt[(i,j)]=ans\n",
    "        \n",
    "            return ans\n",
    "        res=f(n,target)\n",
    "        \n",
    "        # print(dt)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:     # 3888ms\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = defaultdict(int)\n",
    "\n",
    "        lower, upper = -sum(nums), sum(nums)\n",
    "        # bound \n",
    "        for i in range(lower, upper+1):\n",
    "            if i == nums[0]: dp[(0, i)] += 1\n",
    "            if i == -nums[0]: dp[(0, i)] += 1\n",
    "            \n",
    "        # iteration \n",
    "        for i in range(1, n):\n",
    "            for j in range(lower, upper+1):\n",
    "                dp[(i, j)] = dp[(i-1, j-nums[i])] + dp[(i-1, j+nums[i])]\n",
    "        \n",
    "        return dp[(n-1, target)]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = 0\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        # 动态规划，0/1背包，分成两堆，使两堆数的差为target\n",
    "        n = len(nums)\n",
    "        goal = (sum(nums)-target)/2\n",
    "        if goal!=int(goal):return 0\n",
    "        goal = int(goal)\n",
    "        # 找到和为goal的所有组合\n",
    "        # 尝试记忆化搜索\n",
    "        @cache\n",
    "        def dfs(i, c):\n",
    "            if i<0:\n",
    "                return 1 if c==0 else 0\n",
    "            if c<nums[i]:\n",
    "                return dfs(i-1, c)\n",
    "            return dfs(i-1, c)+dfs(i-1, c-nums[i])\n",
    "        return dfs(n-1, goal)\n",
    "\n",
    "        # dp[i][j]表示前i个数中能够组成j的"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        target += sum(nums)\n",
    "        if target < 0 or target % 2:\n",
    "            return 0\n",
    "        target //= 2\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, c):\n",
    "            if i < 0:\n",
    "                return 1 if c == 0 else 0\n",
    "            if c < nums[i]:\n",
    "                return dfs(i - 1, c)\n",
    "            return dfs(i - 1, c) + dfs(i - 1, c - nums[i])\n",
    "\n",
    "        return dfs(len(nums) - 1, target)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        # p \n",
    "        # s - p\n",
    "        # 2p - s = t\n",
    "        # p = (s + t) / 2\n",
    "\n",
    "        target, rest = divmod(sum(nums) + target, 2)\n",
    "        if rest:\n",
    "            return 0\n",
    "        @cache\n",
    "        def dfs(i, c):\n",
    "            if i == len(nums):\n",
    "                return int(c == 0)\n",
    "            if nums[i] > c:\n",
    "                return dfs(i + 1, c)\n",
    "            return dfs(i + 1, c - nums[i]) + dfs(i + 1, c)\n",
    "\n",
    "        return dfs(0, target)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "    n = len(nums)\n",
    "    cache = {i: {} for i in range(n)}\n",
    "\n",
    "    def dfs(i, sum):\n",
    "      if i >= n: return 1 if sum == target else 0\n",
    "      if sum not in cache[i].keys():\n",
    "        cache[i][sum] = dfs(i + 1, sum - nums[i]) + dfs(i + 1, sum + nums[i])\n",
    "      return cache[i][sum]\n",
    "    \n",
    "    return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        res = sum(nums)\n",
    "        if (res+target)%2!=0:\n",
    "            return 0\n",
    "        res = (res+target)//2\n",
    "        ans = 0\n",
    "        @cache\n",
    "        def dfs(i,n):\n",
    "            nonlocal ans\n",
    "            if i<0:\n",
    "                return 1 if n==0 else 0\n",
    "            if n>=nums[i]:\n",
    "                return dfs(i-1,n-nums[i])+dfs(i-1,n)\n",
    "            return dfs(i-1,n)\n",
    "        return  dfs(len(nums)-1,res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        target1 = target + sum(nums)\n",
    "        if target1 < 0 or target1%2 == 1: return 0\n",
    "        target1 = target1 // 2\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,c):\n",
    "            if i < 0 : return 1 if c == 0 else 0\n",
    "            if c < nums[i]: return dfs(i-1,c)\n",
    "            return dfs(i-1,c) + dfs(i-1,c-nums[i]) \n",
    "        return dfs(len(nums)-1, target1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        @functools.lru_cache(None)\n",
    "        def _find(istart, tsum, target):\n",
    "            '''\n",
    "            大于等于istart的地方，才可能取负\n",
    "            tsum: 和（从开始到istart+从istart开始所有地方都为正）\n",
    "            '''\n",
    "            if istart<len(nums) and nums[istart] == 0:\n",
    "                return _find(istart+1, tsum, target)\n",
    "\n",
    "            if tsum <= target:\n",
    "                return int(tsum == target)\n",
    "            if istart >= len(nums):\n",
    "                return 0\n",
    "\n",
    "            c1 = _find(istart+1, tsum, target)\n",
    "            c2 = _find(istart+1, tsum-2*nums[istart], target)\n",
    "            return c1+c2\n",
    "            '''\n",
    "            c = 0\n",
    "            for i in range(istart, len(nums)):\n",
    "                if nums[i] == 0:\n",
    "                    break\n",
    "                ts = tsum - 2*nums[i]\n",
    "                c += _find(i+1, ts, target)\n",
    "            return c\n",
    "            '''\n",
    "        \n",
    "        c0 = nums.count(0)\n",
    "        res = _find(0, sum(nums), target)\n",
    "        res *= 2**c0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[[-1 for _ in range(2010)] for _ in range(n+1)]\n",
    "        def dfs(idx,count):\n",
    "            if idx==n:\n",
    "                if count==target:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            if dp[idx][count+1000]!=-1:\n",
    "                return dp[idx][count+1000]\n",
    "            dp[idx][count+1000]=dfs(idx+1,count-nums[idx])+dfs(idx+1,count+nums[idx])\n",
    "            return dp[idx][count+1000]\n",
    "        return dfs(0,0)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[[-1 for _ in range(2010)] for _ in range(n+1)]\n",
    "        def dfs(idx,count):\n",
    "            if idx==n:\n",
    "                if count==target:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            if dp[idx][count+1000]!=-1:\n",
    "                return dp[idx][count+1000]\n",
    "            dp[idx][count+1000]=dfs(idx+1,count-nums[idx])+dfs(idx+1,count+nums[idx])\n",
    "            return dp[idx][count+1000]\n",
    "        return dfs(0,0)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def findTargetSumWays(self, nums, target):\n",
    "\n",
    "        target += sum(nums)\n",
    "        if target < 0 or target&1:\n",
    "            return 0\n",
    "\n",
    "        target = int(target/2)\n",
    "        n = len(nums)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,s):\n",
    "            if s > target:\n",
    "                return 0\n",
    "            if i == n:\n",
    "                return 1 if s == target else 0\n",
    "\n",
    "            return dfs(i+1,s+nums[i])+dfs(i+1,s)\n",
    "\n",
    "        return dfs(0,0)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        s = sum(nums)\n",
    "        t = s + target\n",
    "        if s < 0:\n",
    "            return 0\n",
    "        if t % 2 == 1:\n",
    "            return 0\n",
    "        t //= 2\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def bt(i, c):\n",
    "            if i == n:\n",
    "                return 1 if c == t else 0\n",
    "            elif c > t:\n",
    "                return 0\n",
    "            else:\n",
    "                return bt(i + 1, c) + bt(i + 1, c + nums[i])\n",
    "        \n",
    "        return bt(0, 0)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#16：51\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        s = sum(nums)\n",
    "        st = s+target\n",
    "        if s<abs(target) or st%2 != 0:return 0\n",
    "        # if s==target:return 1 # 忘记还有0了，归并到下述情况\n",
    "        ##Key:考虑空集的情况\n",
    "        ans = 1 if st==0 else 0\n",
    "        s = st//2\n",
    "        state = deque()\n",
    "        state.append(s)\n",
    "        nums = nums\n",
    "        for i in nums:\n",
    "            for k in list(state):\n",
    "                if k==i:ans += 1\n",
    "                if k-i>=0:state.append(k-i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        \n",
    "        mem = {}\n",
    "        n = len(nums)\n",
    "        def dp(i, j):\n",
    "            # if i < 0:\n",
    "            #     return 0 if j != 0 else 1\n",
    "            if i == 0:\n",
    "                if nums[i] == 0 and j == 0:\n",
    "                    return 2\n",
    "                if abs(j) == abs(nums[i]):\n",
    "                    return 1\n",
    "                return 0\n",
    "\n",
    "            if (i, j) in mem:\n",
    "                return mem[i, j]\n",
    "            mem[i, j] = dp(i - 1, j - nums[i]) + dp(i - 1, j + nums[i])\n",
    "            return mem[i, j]\n",
    "\n",
    "        return dp(n - 1, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        sum_total = sum(nums)\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        @cache\n",
    "        def dfs(sums,u):\n",
    "            if u == n:\n",
    "                return 1 if sums == target else 0\n",
    "\n",
    "            l = dfs(sums - nums[u],u+1)\n",
    "            r = dfs(sums + nums[u],u+1)\n",
    "            return l+r\n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = defaultdict(int)\n",
    "        dp[(-1, 0)] = 1\n",
    "        for i in range(n):\n",
    "            for j in range(-2000, 2000+1): \n",
    "                dp[(i, j)] = dp[(i-1, j-nums[i])] + dp[(i-1, j+nums[i])]\n",
    "\n",
    "        return dp[(n-1, target)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# ### my:dP(思路错误)\n",
    "# class Solution:\n",
    "#     def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "#         if sum(nums)<abs(target):return 0\n",
    "#         dp=[0]*(target+1)\n",
    "#         dp[0]=1\n",
    "#         n=len(nums)\n",
    "#         for x in range(n):\n",
    "#             cp=[0]*(target+1)\n",
    "#             for y in range(1,target+1):\n",
    "#                 cp[y]=cp[y-1]\n",
    "#                 if 1<=y-x<=target:\n",
    "#                     cp[y]+=dp[y-x]\n",
    "#                 if 1<=y+x<=target:\n",
    "#                     cp[y]+=dp[y+x]\n",
    "#             dp=cp\n",
    "#         return dp[target]\n",
    "\n",
    "# ###官思：DP\n",
    "# class Solution:\n",
    "#     def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "#         # if sum(nums)<abs(target):return 0\n",
    "#         # neg=(sum(nums)-target)//2\n",
    "#         su=sum(nums)\n",
    "#         ### eg:[7,9,3,8,0,2,4,8,3,9],0\n",
    "#         if su<target or (su-target)%2:return 0\n",
    "#         neg=(su-target)//2\n",
    "#         dp=[1]+[0]*neg\n",
    "#         n=len(nums)\n",
    "#         for i in range(1,n+1):\n",
    "#             cp=[0]*(neg+1)\n",
    "#             # cp[0]=dp[0]\n",
    "#             # if nums[i-1]==0:\n",
    "#             #     cp[0]+=dp[0]\n",
    "#             # for j in range(1,neg+1):\n",
    "#             for j in range(neg+1):### start from 0, eg[1,0],1\n",
    "#                 cp[j]=dp[j]\n",
    "#                 if j>=nums[i-1]:\n",
    "#                     cp[j]+=dp[j-nums[i-1]]\n",
    "#             dp=cp\n",
    "#         return dp[-1]\n",
    "\n",
    "# ### 官思：DP--优化版\n",
    "# class Solution:\n",
    "#     def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "#         su=sum(nums)\n",
    "#         if (su-target)%2 or su<target:return 0\n",
    "#         neg=(su-target)//2\n",
    "#         dp=[1]+[0]*neg \n",
    "#         for num in nums:\n",
    "#             # for j in range(neg,-1,-1):\n",
    "#             for j in range(neg,num-1,-1): ### 剔除多余遍历\n",
    "#                 # if j>=num:\n",
    "#                 dp[j]+=dp[j-num]\n",
    "#         return dp[-1]\n",
    "\n",
    "# ### S-code\n",
    "# class Solution:\n",
    "#     def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "#         #pos neg\n",
    "#         #pos+neg=total\n",
    "#         #pos-neg=target\n",
    "        \n",
    "#         total=sum(nums)\n",
    "#         if abs(target)>total:\n",
    "#             return 0\n",
    "#         if (total+target)%2==1:\n",
    "#             return 0\n",
    "#         elif (total-target)%2==1:\n",
    "#             return 0\n",
    "#         pos=(total+target)//2\n",
    "#         neg=(total-target)//2\n",
    "\n",
    "#         cap=min(pos,neg)\n",
    "        \n",
    "\n",
    "\n",
    "#         dp=[0]*(cap+1)\n",
    "#         dp[0]=1\n",
    "#         for num in nums:\n",
    "#             for j in range(cap,num-1,-1):\n",
    "#                 dp[j]+=dp[j-num]\n",
    "        \n",
    "#         return dp[cap]\n",
    "\n",
    "\n",
    "# ###回溯---超时\n",
    "# # from functools import lru_cache\n",
    "# class Solution:\n",
    "#     def findTargetSumWays(self,nums,target):\n",
    "#         su=sum(nums)\n",
    "#         n=len(nums)\n",
    "#         if (su-target)%2 or su<abs(target):return 0\n",
    "#         self.ans=0\n",
    "#         # @functools.lru_cache(None)# 不能使用，结果出错[0,35,32,3,4,16,12,25,47,9,14,29,7,26,17,42,21,23,48,18]，20正确结果：20 返回：1\n",
    "\n",
    "#         def dfs(i,cul):\n",
    "#             if i==n:\n",
    "#                 if cul==target:\n",
    "#                     self.ans+=1\n",
    "#                 return\n",
    "#             dfs(i+1,cul+nums[i])\n",
    "#             dfs(i+1,cul-nums[i])\n",
    "\n",
    "#         dfs(0,0)\n",
    "#         return self.ans\n",
    "\n",
    "### 改造版：记忆搜索（参考如下）\n",
    "# https://leetcode.cn/problems/YaVDxD/solution/by-flix-n3q2/\n",
    "class Solution:\n",
    "    def findTargetSumWays(self,nums,target):\n",
    "        su=sum(nums)\n",
    "        n=len(nums)\n",
    "        if (su-target)%2 or su<abs(target):return 0\n",
    "\n",
    "        mp={}\n",
    "        def dfs(i,cul):\n",
    "            if i==n:\n",
    "                if cul==target:\n",
    "                    return 1\n",
    "                return 0\n",
    "            if (i,cul) in mp:\n",
    "                return mp[(i,cul)]\n",
    "\n",
    "            cnt=0\n",
    "            cnt+=dfs(i+1,cul+nums[i])\n",
    "            cnt+=dfs(i+1,cul-nums[i])\n",
    "\n",
    "            mp[(i,cul)]=cnt\n",
    "            return cnt\n",
    "\n",
    "        return dfs(0,0)\n",
    "\n",
    "\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        s = sum(nums)\n",
    "        n = len(nums)\n",
    "        tar = target\n",
    "        tar += s\n",
    "        if tar < 0 or tar & 1 == 1:\n",
    "            return 0\n",
    "        tar //= 2\n",
    "        @cache\n",
    "        def dfs(i, load):\n",
    "            if i < 0:\n",
    "                return 1 if load == 0 else 0\n",
    "            if tar < nums[i]:\n",
    "                return dfs(i - 1, load)\n",
    "            return dfs(i - 1, load - nums[i]) + dfs(i - 1, load)\n",
    "        return dfs(n -1, tar)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        @cache\n",
    "        def dp(i, t):\n",
    "            if i == 0:\n",
    "                res = 0\n",
    "                if t == nums[i]:\n",
    "                    res += 1\n",
    "                if t == -nums[i]:\n",
    "                    res += 1\n",
    "                return res\n",
    "            return dp(i - 1, t + nums[i]) + dp(i - 1, t - nums[i])\n",
    "        return dp(len(nums) - 1, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        t = target + sum(nums)\n",
    "        if t < 0 or t % 2:\n",
    "            return 0\n",
    "        t //= 2\n",
    "        \n",
    "        # + :p\n",
    "        # - :s - p\n",
    "        # p-(s-p)=t => p = (s+t)/2\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, c):\n",
    "            if i < 0:\n",
    "                return 1 if c == 0 else 0\n",
    "            return dfs(i - 1, c) + dfs(i - 1, c - nums[i])\n",
    "        \n",
    "        return dfs(n - 1, t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        s = sum(nums)\n",
    "        if (s + target) % 2 == 1: return 0\n",
    "        d = (s + target) // 2\n",
    "        L = len(nums)\n",
    "        @lru_cache(None)\n",
    "        def f(t, u):\n",
    "            if t == L:\n",
    "                return 1 if u == d else 0\n",
    "            return f(t + 1, u + nums[t]) + f(t + 1, u)\n",
    "        return f(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        memo = dict()\n",
    "\n",
    "        def dp(n, target):\n",
    "            if n == 0 :\n",
    "                return 1 if target == 0 else 0\n",
    "\n",
    "            if (n, target) not in memo:\n",
    "                memo[(n, target)] = dp(n-1,target-nums[n-1]) + dp(n-1, target + nums[n-1])\n",
    "                \n",
    "            return memo[(n, target)]\n",
    "        \n",
    "        res = dp(len(nums), target)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        # target = abs(target)\n",
    "        # sumnum = sum(nums)\n",
    "        # dp = [[0]*(sumnum+2) for _ in range(len(nums))]\n",
    "        # if target > sumnum:\n",
    "        #     return 0\n",
    "        # # 当物品为0时\n",
    "        # for j in range(sumnum+2):\n",
    "        #     if j == abs(nums[0]):\n",
    "        #         if nums[0] == 0:\n",
    "        #             dp[0][j] = 2\n",
    "        #         else:\n",
    "        #             dp[0][j] = 1\n",
    "        \n",
    "        # for i in range(1,len(nums)):\n",
    "        #     for j in range(sumnum+1):\n",
    "        #         if j == 0:\n",
    "        #             dp[i][0] = 2*dp[i-1][abs(nums[i])]\n",
    "        #         else:\n",
    "        #             if j+nums[i] <= sumnum:\n",
    "        #                 dp[i][j] = dp[i-1][abs(j-nums[i])] + dp[i-1][j+nums[i]]\n",
    "        #             else:\n",
    "        #                 dp[i][j] = dp[i-1][abs(j-nums[i])]\n",
    "        # return dp[len(nums)-1][target]\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,target):\n",
    "            if i == 0:\n",
    "                if nums[i] == abs(target):\n",
    "                    if target == 0:\n",
    "                        return 2\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            else:\n",
    "                return dfs(i-1,target-nums[i]) + dfs(i-1,target+nums[i])\n",
    "\n",
    "        return dfs(len(nums)-1,target)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        t = target + sum(nums)\n",
    "        if t < 0 or t % 2:\n",
    "            return 0\n",
    "        t //= 2\n",
    "        \n",
    "        # + :p\n",
    "        # - :s - p\n",
    "        # p-(s-p)=t => p = (s+t)/2\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, c):\n",
    "            if i == n:\n",
    "                return 1 if c == t else 0\n",
    "            return dfs(i + 1, c) + dfs(i + 1, c + nums[i])\n",
    "        \n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        al=[]\n",
    "        bl=[]\n",
    "        c=sum(nums)\n",
    "        for i in nums:\n",
    "            \n",
    "            if al:\n",
    "                for j in al:\n",
    "                    if j+c<target or j-c>target:\n",
    "                        continue\n",
    "                    else:\n",
    "                        bl.append(j+i)\n",
    "                        bl.append(j-i)\n",
    "                al=bl\n",
    "                bl=[]\n",
    "            else:\n",
    "                al=[i,-i]\n",
    "            c-=i\n",
    "        return al.count(target)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums, target: int) -> int:\n",
    "        # 做个优化，就是将已有的结果放入哈希表中\n",
    "        if sum(nums)<target:\n",
    "            return 0\n",
    "        if sum(nums)<-target:\n",
    "            return 0\n",
    "        dp={}\n",
    "        def dfs(i, target_p):\n",
    "            if i == len(nums) and target_p != 0:\n",
    "                return 0\n",
    "            elif target_p == 0 and i == len(nums):\n",
    "                return 1\n",
    "            if (i,target_p) in dp:\n",
    "                return dp[(i,target_p)]\n",
    "            dp[(i,target_p)] = dfs(i + 1, target_p + nums[i])+dfs(i + 1, target_p - nums[i])\n",
    "            return dp[(i,target_p)]\n",
    "\n",
    "        res = 0\n",
    "        res += dfs(0, target)\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        dp = [[-1 for _ in range(4001)] for _ in range(20)]\n",
    "\n",
    "        def get_result(right: int, tar: int) -> int:\n",
    "            if right == 0:\n",
    "                dp[right][tar + 2000] = (tar == nums[0]) + (tar == -nums[0])\n",
    "            elif dp[right][tar + 2000] < 0:\n",
    "                dp[right][tar + 2000] = get_result(right - 1, tar + nums[right]) + \\\n",
    "                                 get_result(right - 1, tar - nums[right])\n",
    "            return dp[right][tar + 2000]\n",
    "\n",
    "        result = get_result(len(nums) - 1, target)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        lls = 0\n",
    "        # ll =[]\n",
    "        dd = {}\n",
    "        def digui(ll, idx):\n",
    "            nonlocal lls\n",
    "            if idx == n:\n",
    "                # print(ll)\n",
    "                # if ll == target:\n",
    "                #     lls += 1\n",
    "                # return\n",
    "                return 1 if ll == target else 0\n",
    "            # if idx not in dd:\n",
    "            else:\n",
    "                if (ll,idx) not in dd:\n",
    "                    A = digui(ll+nums[idx], idx+1) \n",
    "                    B = digui(ll-nums[idx], idx+1)\n",
    "                    dd[(ll, idx)] = A + B\n",
    "                \n",
    "                return dd[(ll,idx)] \n",
    "            \n",
    "        return digui(0, 0)\n",
    "        # return lls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        memo = {}\n",
    "\n",
    "        def dp(i, remain):\n",
    "            if i == len(nums):\n",
    "                if remain == 0:\n",
    "                    return 1\n",
    "                return 0\n",
    "            \n",
    "            if (i, remain) in memo:\n",
    "                return memo[(i, remain)]\n",
    "            \n",
    "            result = dp(i+1, remain - nums[i]) + dp(i+1, remain + nums[i])\n",
    "            memo[(i, remain)] = result\n",
    "            return result\n",
    "        \n",
    "        return dp(0, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        memo = dict()\n",
    "        def dp(n, target):\n",
    "            if n == 1:\n",
    "                # 这里返回的是target == nums[0] 和 target == -nums[0]的个数\n",
    "                return (target == nums[0]) + (target == -nums[0])\n",
    "            if f\"{n}_{target}\" in memo:\n",
    "                return memo[f\"{n}_{target}\"]\n",
    "            res = dp(n-1, target - nums[n-1]) + dp(n-1, target + nums[n-1])\n",
    "            memo[f\"{n}_{target}\"] = res\n",
    "            return res\n",
    "        res = dp(len(nums),target)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        memo = dict()\n",
    "        def dp(n, target):\n",
    "            if n == 1:\n",
    "                return (target == nums[n-1]) + (target == -nums[n-1])\n",
    "            if f\"{n}_{target}\" in memo:\n",
    "                return memo[f\"{n}_{target}\"]\n",
    "            res = dp(n-1, target - nums[n-1]) + dp(n-1, target + nums[n-1])\n",
    "            memo[f\"{n}_{target}\"] = res\n",
    "            return res\n",
    "        res = dp(len(nums),target)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        dp = {}\n",
    "    \n",
    "        def dfs(index,cur):\n",
    "            if (index,cur) in dp:return dp[(index,cur)]\n",
    "            if index >= len(nums):\n",
    "                return 1 if cur == target else 0\n",
    "            conditions = dfs(index + 1,cur + nums[index]) + dfs(index + 1,cur - nums[index])\n",
    "            dp[(index,cur)] = conditions\n",
    "            return conditions\n",
    "        return dfs(0,0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        @cache\n",
    "        def dfs(l,r,t):\n",
    "            if l == r:\n",
    "                return int(nums[l] == t)+int(nums[l] == -t)\n",
    "            return dfs(l+1,r,t-nums[l])+dfs(l+1,r,t+nums[l])\n",
    "        n = len(nums)\n",
    "        return dfs(0,n-1,target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        @functools.lru_cache(None) \n",
    "        def f(i, t):\n",
    "            if i == 0:\n",
    "                return 1 if t == 0 else 0\n",
    "            return f(i - 1, t + nums[i - 1]) + f(i - 1, t - nums[i - 1])\n",
    "\n",
    "        return f(len(nums), target)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:    \n",
    "        @cache    \n",
    "        def dfs(i, remain):\n",
    "            if i == 0:\n",
    "                return int(remain == 0)\n",
    "            return dfs(i - 1, remain + nums[i - 1]) + dfs(i - 1, remain - nums[i - 1])\n",
    "        return dfs(len(nums), target)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], S: int) -> int:\n",
    "        @functools.lru_cache(None)\n",
    "        def dp(idx,target):\n",
    "            if idx<0:\n",
    "                return 1 if target==0 else 0\n",
    "            a=dp(idx-1,target-nums[idx])\n",
    "            b=dp(idx-1,target+nums[idx])\n",
    "            return a+b\n",
    "        return dp(len(nums)-1,S)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetSumWays(self, nums: List[int], target: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i: int, s: int) -> int:\n",
    "            if i < 0:\n",
    "                return 0 if s else 1\n",
    "            return dfs(i - 1, s + nums[i]) + dfs(i - 1, s - nums[i])\n",
    "        \n",
    "        return dfs(len(nums) - 1, target)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
